
function
SlkTree ()
{              
    var  root = null;
    var  parse_stack = new Stack();

function
Node ( _symbol )
{
    this.symbol = _symbol;
    this.parent = null;         // parent is the lhs of the production
    this.child = null;          // first symbol on rhs of production
    this.sibling = null;        // rest of the parent production is siblings
    this.left_sibling = null;   // to go backwards
}

function
Stack () {
    var  STACKSIZE = 1024;
    var  start = new Array (STACKSIZE);
    var  top = STACKSIZE - 1;
    var  end = STACKSIZE;

    this.pop = function()
    {
        var  value = null;

        if ( top < end ) {
            value = start[top++];
        }
        return  value;
    }

    this.push = function ( node )       { start [--top] = node; }
}

function
make_LL_branch ( production_number )
{
    var     prev = null;
    var     child = null;
    var     production = GetProductionArray ( production_number );
    var     rhs;
    var     length,
            index = 0,
            debug = 0,
            rhs_length;

    rhs_length = production [ index++ ] - 1;
    for ( length = rhs_length;  length > 0;  --length ) {
        rhs = production [ ++index ];               // skip over lhs
        if ( debug > 0 ) {
            console.log ( "rhs = " + GetSymbolName ( rhs ) );
        } 
        if ( IsAction ( rhs ) ) {
            continue;                               // skip actions
        }
        prev = new Node ( rhs );
        child = prev;
        for ( --length;  length > 0;  --length ) {
            rhs = production [ ++index ];
            if ( debug > 0 ) {
                console.log ( "rhs = " + GetSymbolName ( rhs ) + " " + rhs );
            }
            if ( IsAction ( rhs ) ) {
                continue;                           // skip actions
            }
            prev.sibling = new Node ( rhs );
            prev.sibling.left_sibling = prev;
            prev = prev.sibling;
        }
    }                 
    for (;  prev != null;  prev = prev.left_sibling ) {
        if ( IsNonterminal ( prev.symbol ) ) {
            parse_stack.push ( prev );                 // copy parsing pushes
        }              
    }

    return  child;
}

this.predict = function ( production_number )
{
    var     parent;
    var     child;
    var     production = GetProductionArray ( production_number );

    // console.log ( GetProductionName ( production_number ) );
    if ( root == null ) {                                    // first call
        root = new Node ( production [ 1 ] );                // lhs
        parse_stack.push ( root );
    }
    parent = parse_stack.pop ();
    child = make_LL_branch ( production_number );
    if ( child != null  &&  parent != null ) {
        parent.child = child;
        child.parent = parent;
    }
}

this.reduce = function ( production_number )
{
    var     prev = null;
    var     child = null;
    var     this_child = null;
    var     production = GetProductionArray ( production_number );
    var     rhs;
    var     length,
            index = 0,
            debug = 0,
            rhs_length;

    // console.log ( GetProductionName ( production_number ) );
    rhs_length = production [ index++ ] - 1;
    for ( length = rhs_length;  length > 0;  --length ) {
        rhs = production [ ++index ];               // skip over lhs
        if ( IsAction ( rhs ) ) {
            continue;                               // skip actions
        }
        prev = new Node ( rhs );
        this_child = prev;
        for ( --length;  length > 0;  --length ) {
            rhs = production [ ++index ];
            if ( IsAction ( rhs ) ) {
                continue;                           // skip actions
            }
            prev.sibling = new Node ( rhs );
            prev.sibling.left_sibling = prev;
            prev = prev.sibling;
        }
    }
    for (;  prev != null;  prev = prev.left_sibling ) {
        if ( IsNonterminal ( prev.symbol ) ) {
            child = parse_stack.pop ();
            if ( child != null ) {
                if ( debug > 0 ) {
                    console.log ( "pop :   " + GetSymbolName ( child.symbol ) );
                } 
                prev.child = child;
                child.parent = prev;
            } else {
                if ( debug > 0 ) {
                    console.log ( "pop :   null" );
                } 
            }
        }
    }
    if ( this_child != null ) {
        if ( debug > 0 ) {
            console.log ( "push:   " + GetSymbolName ( this_child.symbol ) );
        }
    } else {
        if ( debug > 0 ) {
            console.log ( "push:   null" );
        }              
    }
    parse_stack.push ( this_child );
    if ( production_number == 1 ) {
        root = new Node ( production [ 1 ] );                // lhs
        root.child = this_child;
        if ( this_child != null ) {
            this_child.parent = root;
        }
    }
}

show_tree = function ( tree )
{
    var   child,
          sibling;

    if ( tree == null ) {
        return;
    }
    console.log ( GetSymbolName ( tree.symbol ) );

    child = tree.child;

    if ( child != null ) {
        show_tree ( child );
    
        for ( sibling = child.sibling;  sibling != null;  sibling = sibling.sibling ) {
            show_tree ( sibling );
        }
    }
}

this.show_tree = function()
{
    show_tree ( root );
}

this.show_parse_derivation = function()
{
    show_parse_derivation ( root );
}

show_parse_derivation = function ( tree )
{
    var   child,
          sibling;
    var   string;

    if ( tree == null ) {
        return;
    }
    string = ( GetSymbolName ( tree.symbol ) + " -> ");

    child = tree.child;

    if ( child != null ) {
        string += ( GetSymbolName ( child.symbol ) + "  " );
        for ( sibling = child.sibling;  sibling != null;  sibling = sibling.sibling ) {
            string += ( GetSymbolName ( sibling.symbol ) + "  " );
        }
        console.log ( string );
    
        if ( IsNonterminal ( child.symbol ) ) {
            show_parse_derivation ( child );
        } 

        for ( sibling = child.sibling;  sibling != null;  sibling = sibling.sibling ) {
            if ( IsNonterminal ( sibling.symbol ) ) {
                show_parse_derivation ( sibling );
            }
        }
    } else { 
        console.log ( string );
    }
}


}
